package LeetCode;

import com.company.LinkList.LIstTest;
import sun.reflect.generics.tree.Tree;

import java.util.*;

public class LeetCode107 {
     public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
     }
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
         // 这不能处理同层的问题
//         if (root == null){
//             return null;
//         }
//        TreeNode node = root;
//        Queue<TreeNode> queue = new LinkedList<>();
//        List<List<Integer>> res = new ArrayList<>();
//        List<Integer> start = new ArrayList<>();
//        start.add(node.val);
//        res.add(start);
//        queue.offer(root);
//        while (!queue.isEmpty()){
//            node = queue.poll();
//            List<Integer> list = new ArrayList<>();
//
//            TreeNode left = node.left;
//            TreeNode right = node.right;
//            if (left != null){
//                list.add(left.val);
//                queue.add(left);
//            }
//            if (right != null){
//                list.add(right.val);
//                queue.add(right);
//            }
//            if (list.size() != 0) {
//                res.add(list);
//            }
//        }
//        return res;

        if (root == null){
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<List<Integer>> res = new ArrayList<>();
        Stack<Integer> len = new Stack<>();// 每层的计数
        Stack<Integer> stack = new Stack<>();
        while (!queue.isEmpty()){
            int n = queue.size();
            len.add(n);
            for (int i = 0; i < n; i++){
                stack.add(queue.peek().val);
                TreeNode node = queue.poll();
                if (node.right != null){
                    queue.offer(node.right);
                }
                if (node.left != null){
                    queue.offer(node.left);
                }
            }
        }
        while (!len.isEmpty()){
            int l = len.pop();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < l; i++){
                list.add(stack.pop());
            }
            res.add(list);
        }
        return res;
    }


    public static void main(String[] args) {
        TreeNode node = new TreeNode(3);
        node.left = new TreeNode(9);
        node.right = new TreeNode(20);
        node.right.left = new TreeNode(15);
        node.right.right = new TreeNode(7);
        new LeetCode107().levelOrderBottom(node);
    }
}
